package fun.coding.leetcode;

import java.util.Arrays;
import java.util.List;

import fun.coding.baozi.practice.BinaryTreeHelper;

public class FlattenBinaryTreeToLinkedList {

	public static void main(String[] args) {
		FlattenBinaryTreeToLinkedList instance = new FlattenBinaryTreeToLinkedList();
		/*
		 *       1
		 *     2   5
		 *   3  4    6    
		 */
		String[] test1 = {"1", "2", "5", "3", "4", "#", "6"};
		TreeNode root1 = BinaryTreeHelper.deserializeBinaryTree(Arrays.asList(test1));
		
		// instance.flatten(root1);
		TreeNode t = instance.flattenInorder(root1);
		List<String> res = BinaryTreeHelper.serializeBinaryTree(t);
		for (String s : res) {
			System.out.print(s + ", ");
		}
	}

	// Keep this last visited to keep the parent
	private TreeNode lastVisitedNode = null;

	/**
	 *    1
	 *  2     ---> caution: might cause stack overflow, since after the left part change,
	 *     1
	 *       2, and then 2's right point to itself. 
	 *  
	 */
	public void flatten(TreeNode root) {
		if (root == null) return;
		
		if (lastVisitedNode != null) {
			lastVisitedNode.right = root;
			lastVisitedNode.left = null;
		}
		
		lastVisitedNode = root;
		// Here we have to keep the old right pointer, or else it might change during the left part
		TreeNode oldRight = root.right;
		flatten(root.left);
		flatten(oldRight);
	}
	
	private TreeNode last = null;
	private TreeNode newHead = null;
	// Flatten it inorder, and return the new head
	public TreeNode flattenInorder(TreeNode root) {
		if (root == null) return null;
		
		flattenInorder(root.left);
		
		TreeNode oldRight = root.right;
		if (last == null) {
			newHead = root;
		} else {
			last.right = root;
			last.left = null;
		}
		last = root;
		flattenInorder(oldRight);
		
		return newHead;
	}
}
